#include <stdio.h>
#include <string.h>

#define INF 0x3f3f3f
#define MAXV 7

/**
 * Dijkstra算法
 * 求带权图（所有权值均为正数）中一个订单到其余各个顶点的最短路径
 * 也称单源最短路径算法
 */

typedef struct Graph
{
    int n;
    int edges[MAXV][MAXV];
} Graph;


/**
 * 打印所有最短路径
 */
void printAllPath(Graph g, int S[], int distances[], int path[], int v) {
    int i, j; // 循环参数
    int k; // 存储前继节点
    int apath[MAXV], d;    // 存储一条最短路径
    for (i = 0; i < g.n; i++) {
        if (S[i] == 1 && i != v) {
            printf("from %d to %d min distance : %d \t path: ", v, i, distances[i]);
            // 添加终点
            d = 0;
            apath[d] = i;
            // 存储前继节点
            k = path[i];
            if (k == -1) {
                printf("no path\n");
            } else {
                // 递归的向前找到起点
                while (k != v)
                {
                    d++;
                    apath[d] = k;
                    k = path[k];
                }
            }
            // 添加起点
            d++;
            apath[d] = v;
            // 输出起点
            printf("%d", apath[d]);
            // 递归的输出路径
            for (j = d-1; j >= 0; j--) {
                printf("->%d", apath[j]);
            }
            printf("\n");
        }
    }
}

// Dijkstra
void dijkstra(Graph g, int v) {
    int S[MAXV]; // S[i]==1表示i在S中，0表示i在U中
    int distances[MAXV];    // distances[i]表示从v到i的最短距离
    int path[MAXV]; // path[i]表示从v到i的最短路径的前驱节点
    
    // 初始化S
    memset(S, 0, sizeof(S));
    // 初始化distances和path
    for (int i = 0; i < g.n; i++)
    {
        distances[i] = g.edges[v][i];
        if (distances[i] == INF) {
            path[i] = -1;
        } else {
            path[i] = v;
        }
    }

    // 把v加入S
    S[v] = 1;

    // 考虑v到其他n-1个顶点的最短路径
    for (int i = 0; i < g.n - 1; i++) {
        // 找出到S最短路径的顶点，将其加入到S中
        int minDist = INF;
        int k;
        for (int j = 0; j < g.n; j++) {
            if (S[j] == 0 && distances[j] < minDist) {
                minDist = distances[j];
                k = j;
            }
        }
        // 把k加入S
        S[k] = 1;

        // 更新distances和path
        for (int j = 0; j < g.n; j++) {
            if (g.edges[k][j] < INF && distances[j] > distances[k] + g.edges[k][j]) {
                distances[j] = distances[k] + g.edges[k][j];
                path[j] = k;
            }
        }
    }
    printAllPath(g, S, distances, path, v);
    
}


// 构建无向图
void createGraph(Graph *g)
{
    int i, j;
    g->n = MAXV;
    int adjMatrix[MAXV][MAXV] = {
        {0, 4, 6, 6, INF, INF, INF},
        {INF, 0, 1, INF, 7, INF, INF},
        {INF, INF, 0, INF, 6, 4, INF},
        {INF, INF, 2, 0, INF, 5, INF},
        {INF, INF, INF, INF, 0, INF, 6},
        {INF, INF, INF, INF, 1, 0, 8},
        {INF, INF, INF, INF, INF, INF, 0}};
    for (i = 0; i < MAXV; i++)
    {
        for (j = 0; j < MAXV; j++)
        {
            g->edges[i][j] = adjMatrix[i][j];
        }
    }
}


int main()
{
    Graph g;
    createGraph(&g);
    dijkstra(g, 0);
    return 0;
}




